The present invention relates to a method for the optimization of robust designs using a search engine, and a search engine for implementing such a method. More particularly, the present invention relates to optimization of the design of semiconductor circuit products, and the design of semiconductor product manufacturing processes, where decision making in the search engine is made under uncertainty.
A search engine is an algorithm, typically implemented on a general purpose computer, that traverses a space of possible candidate designs in a manner to try to find one or more improved candidate designs by trying to improve upon one or more objective functions. Search engines can be used to solve complex problems that are intractable and defy direct solution, or for which theoretically known approaches are impractical because they require too much time or other resources or are too inconvenient to bother modeling.
Search engines differ by the search space or design space on which they operate. For example, the design space of a typical parameter search engine is a subset of a multidimensional space of real numbers, i.e. Rn. Other candidate spaces are also possible, for example, data structures such as a tree, a graph, etc.
Search engines are used in a variety of disciplines ranging from academic research to industrial applications. Because of the widespread use of search engines, they have been carefully studied. Techniques have been discovered to improve performance and eliminate unproductive search paths. While some of the techniques and principles are generally applicable, other techniques or refinements are based on the specific nature of the problem in question.
One example of the need to refine search engine techniques is in engineering or industrial design problems in which there is a need to deal with uncertainty. For example, in the large-scale production of any manufacture, real-world considerations such as machine tolerances, individual variation in components and other factors affect the quality and performance of the final product. Such variations can often be regarded as random and modelled, for example, using a Gaussian probability distribution. Robustness is a characteristic of a design that qualifies how well that design performs in the face of variation. A robust design process refers to an approach to reducing the effects of variation by predicting the likely magnitude of such variations and accounting for them in the specifications, models and design of the product.
Since automated search techniques can be used to aid design, it is useful to consider incorporating robustness into automated search in a robust design process.
One well-known approach to robust search problems is the xe2x80x9cbrute-forcexe2x80x9d Monte Carlo search method. Monte Carlo sampling is the process of drawing random samples from a process that has variation. The xe2x80x9cbrute-forcexe2x80x9d Monte Carlo search method replaces a standard objective function with a variation-induced objective function by taking a fixed number of Monte Carlo samples, then performing a statistical estimate on those samples, and trying to optimize those statistical estimates in the same manner as if they were deterministic objective functions. This method is combined with standard search engines that have typically originally been used in search on deterministic objective functions, e.g. evolutionary algorithms and simulated annealing. The xe2x80x9cbrute forcexe2x80x9d Monte Carlo search method is quite problem independent because it is independent of specific characteristics of the underlying variation; it just needs to be able to draw Monte Carlo samples. This makes it a very useful in attacking problems that are not solvable in closed form; it is, in general a very flexible approach to robust optimization, and is sometimes the only conceivable method of robust optimization for particular problems.
As is well known in statistical theory, increasing the sample size can reduce the amount of uncertainty in estimation of the underlying process. Accordingly, the standard technique to reduce the uncertainty in xe2x80x9cbrute-forcexe2x80x9d Monte Carlo search method is to increase the (pre-set) number of samples. Unfortunately, increasing the sample size increases the amount of computing power and other resources required. It is not uncommon to run 50 or even 500 Monte Carlo samples at a design point in order to keep uncertainty low. That means that xe2x80x9cbrute-forcexe2x80x9d Monte Carlo search need roughly 50 to 500 more computational effort than a comparable non-robust search. If the computing demands are excessive, then the finite amount of available resources, including time, may constrain the types of problems that can be solved by this approach. It is, therefore, desirable to provide a method that preserves the utility and power of such search engines while reducing the computing demands and constraints that are associated with existing methods.
Other types of search engines invented for robust design problems employ relatively fast, specialized algorithms that rely on a particular closed form description of the underlying process, or make assumptions about the underlying process. The advantage is that these techniques are able to use less computational effort than a generalized xe2x80x9cbrute forcexe2x80x9d Monte Carlo search method. The drawback is that these approaches are only able to solve a subset of all robust optimization problems.
In summary, the xe2x80x9cbrute forcexe2x80x9d Monte Carlo approach to robust design has the advantage of broad applicability and flexibility, with the disadvantage of needing significant computing resources. The approach of having specialized algorithms for robust design has the advantage of needing less computational resources, with the disadvantage of limited applicability and flexibility. Accordingly, there is a desire to have an approach to robust design that has broad applicability and flexibility, yet requires less computing resources than the xe2x80x9cbrute-forcexe2x80x9d Monte Carlo approach.
It is an object of the present invention to obviate or mitigate at least one disadvantage of previous methods associated with search engines applied to robust design.
The present invention generally provides a method of comparing two or more competing candidate solutions and determining the best candidate within the framework of a search algorithm that incorporates a competition, such as evolutionary computing, simulated annealing, pattern searching with stochastic elements or tabu searching.
The present invention further provides a method of dealing with randomness in the optimization of one or more objective functions in the design of semiconductor products and their related manufacturing processes. This method is applicable to search algorithms having one or more stochastic objective functions. The present invention also provides a system or search engine associated with the above methods.
According to an aspect of the present invention there is provided in robust design problems using a search engine, a method of selecting one of a first and second semiconductor technology design candidates, the method comprising: randomly sampling said first candidate to obtain a first random sample; determining at least one objective function value from said first random sample; randomly sampling said second candidate to obtain a second random sample; determining at least one objective function value from said second random sample; determining, based on said first and second objective function values comparison-oriented statistical estimates relating the first and second design candidates; selecting, if possible, based on at least one decision rule and said comparison-oriented statistical estimates, one of said design candidates; and repeating the previous steps until one of said design candidates has been selected.
According to a second aspect of the present invention, there is provided in robust design problems using a search engine, a computer-readable program product for selecting one of first and second semiconductor technology design candidates based on at least one objective function, the program product comprising: means for randomly sampling said first candidate to obtain a first random sample; means for determining at least one objective function value from said first random sample; means for randomly sampling said second candidate to obtain a second random sample; means for determining at least one objective function value from said second random sample; means for determining, based on said first and second objective function values comparison-oriented statistical estimates relating the first and second design candidates; means for selecting, if possible, based on at least one decision rule and said comparison-oriented statistical estimates, one of said design candidates; and means for repeating the previous steps until one of said design candidates has been selected.
According to another aspect of the present invention there is provided in robust design problems using a search engine, a method of selecting one of a first and second semiconductor technology design candidates, the method comprising: a) defining a population of individuals; b) selecting at least one objective function that defines at least one objective function value for each individual; c) repeatedly performing the following steps until at least one stopping criterion is satisfied: 1) grouping individuals from the population into at least one group for comparison with other individuals in the group, the comparison being on the basis of their at least one objective function values 2) for each group of the at least one groups performing the following: i) for each individual of the at least one groups, sampling each individual at least one time and determining at least one corresponding objective function value; ii) statistically determining, based on the sample objective function values, corresponding statistical estimators of design quality; iii) comparing the sampled individuals within each group on the basis of the statistical estimators of design quality; iv) selecting, if there is enough statistical confidence from the comparison of the statistical estimators, one of the sampled individuals from the at least one group; v) repeating the above steps if a selection has not yet been made; and 3) replacing the population of individuals by a new population consisting of the chosen individuals from each group.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying drawings.